package io.github.handyang.algorithms.graph;

public class TwoColor {
    private static final int RED = 1;
    private static final int BLACK = 2;

    private final Graph graph;
    private final boolean[] marked;
    private final int[] color;

    private boolean twoColorable = true;

    public TwoColor(Graph graph) {
        this.graph = graph;

        this.marked = new boolean[graph.V()];
        this.color = new int[graph.V()];

        this.color[0] = RED;
        dfs(0);
    }

    private void dfs(int start) {
        marked[start] = true;

        for (Integer point : graph.adj(start)) {
            if (!marked[point]) {
                marked[point] = true;
                color[point] = color[start] ^ 3;
                dfs(point);
            } else if (color[point] == color[start]) {
                twoColorable = false;
            }
        }
    }

    public boolean isTwoColorable() {
        return twoColorable;
    }
}
